1. Technical Field
This invention relates to the field of data transmission via discrete multi-tone modulation and, more particularly, to method and apparatus for allocating data for modulation via discrete multiple tones.
2. Description of the Related Arts
In a typical discrete multi-tone modulator, for example, a modulator described by A.N.S.I. Standard T1.413-1995, a plurality of discrete tones are utilized for carrying data modulated thereon. A problem with this approach is that the particular carrier frequencies selected for data modulation may be likewise utilized for, for example, AM radio broadcasts or may already be used by modulators transmitting data on other adjacent cable pairs and the like. Thus, time-varying far end crosstalk and near end crosstalk or cable ingress of noise from external sources can interfere with data transmission of discrete multitone data modulators. For example, in the discrete multi-tone modulation approach, carrier frequencies are spaced approximately every four kilohertz across a broad spectrum of frequencies (for example, from 0-1 megahertz) for data transmission. There may be an AM radio broadcast or a data transmission on an adjacent cable pair at 530 kilohertz that may interfere with a data transmission at approximately the same frequency. The interfering signal creates noise which precludes data transmission at a higher bit carrying capacity than would have been achievable without the presence of the noisy 530 kilohertz interfering signal.
Noise from carrier channels using the same frequencies can thus detract from bit-carrying capacity on those channels. Some tones on the same cable pair can carry more data than other tones (depending on what adjacent cable pairs are carrying and the amount of noise ingress from external sources among other factors). When one views the entire power spectrum, and without any power constraint on the system, one may allocate bits to frequencies freely to fill or pour bits into the power spectrum like water into the peaks and valleys of the spectrum until all frequencies are equally full. In a typical modulator of the multi-tone variety, a channel signal to noise ratio estimation phase is employed. The transmitter sends a known pseudo-random noise sequence to a receiver and the receiver computes the received signal to noise ratio by computing the coherence between the received signal and its stored replica. The characteristics are computed in the form of a ratio of the channel gain to noise for each channel or tone. Let us denote this quantity by gain-to-noise ratio GNR.
Referring briefly to FIG. 1, there is shown such GNR for a series noise spectrum for a series of discrete tones, a+f, a+2f, a+3f . . . , where a represents a displacement frequency from 0 Hertz and f the carrier or tone spacing, for example, approximately 4000 Hz. The GNR plot resembles a "terrain" with peaks and valleys. Some frequencies such as a+f are noisier than other frequencies such as a+6f. Once the GNR is determined, bits are poured into the spectrum (terrain) until a maximum total power level (water level) P is reached. Two power levels, P1 and P2, are shown by way of example. Where a is the initial frequency and f is the tone spacing, then bits are poured on each possible tone until a total power level P is reached above the terrain GNR. For example, for power level P2, bits are poured on or allocated to frequencies: a+2f, a+3f, a+4f, and a+6f. For power level P1, a higher power level, bits may be allocated to all tones except a+7f. This technique is described by Mr. John A. C. Bingham in his paper "Multicarrier Modulation for Data Transmission: An Idea Whose Time Has Come," I.E.E.E. Communications, May, 1990, pp. 5-14, incorporated by reference as to its entire contents.
Bingham goes on to describe a `water filling` bit allocation process that we describe more accurately by the analogy of `ice cube filling`. Bingham's algorithm adds bits one bit a time according to selecting a bit for addition to a bin that is the least expensive in additional power needed. Because the bit added represents a chunk of power, we prefer to call the technique "ice cube filling" instead of a more smooth "water pouring" analogy used by Bingham. The "waterfall," bit "pouring," or even the "ice cube filling" technique for allocating bits to tones of a tone or frequency power spectrum has been practiced for years to advantage. Total power is the primary constraint considered in allocating bits to tones in these approaches. However, as these types of techniques have become more predominant, problems have evolved. For example, these approaches do not take into consideration the allocation of a maximum or minimum number of bits to each tone or frequency bin as will be further described herein or consideration of a power mask for each tone as will be defined herein. These additional constraints can be design imposed or imposed by the standard under which the techniques must operate (such as A.N.S.I. standard T1.413-1995) Thus, there has been felt a need to develop other methods for allocating bits to a power spectrum.